public class question_55 {
}
//这倒题目是关于跳棋的题目，正常人的思路可能是从它的起始位置开始然后遍历，但是这样会造成很多重复的无用计算
//而动态规划就是专门解决这种重复计算问题的，所以我们可以从尾到头进行推到和标记，但一个点跳到某个之前已经跳过的位置，这个位置是之前已经做过标记能不能
//到达最后一个点的，如果这个点已经是false，那就没必要再继续走下去了
class Solution_55 {
    public boolean canJump(int[] nums) {

//        int len=nums.length;
//        if(len==1)
//            return true;//这种情况起点就已经是终点了，当然是true
//        boolean arr[]=new boolean[len];//标记这个点是否能到达最后的终点
//        for (int i = len-2; i >=0 ; i--) {//从后往前
//            //刚开始进来都是false
//            arr[i]=false;
//            int temp=nums[i];
//            if(temp==0){
////                arr[i]=false;//与上面重复了
//                continue;//提前结束本次循环
//            }
//            if(temp>=((len-1)-i)){//这个位置可以直接跳到最后一个
//                arr[i]=true;
//                continue;//提前结束本次循环
//            }
//            //到这一步说明需要寻找中间点来达到最后一步
//            for (int j = 1; j <=temp; j++) {//i+j<=(len-1)这一部判断是防止数组越界的，不能找中间点找到数组外面去了吧，这一个最后还是去掉了，因为上面的那个已经帮我排除了这种情况了
//                //这一步找到它能跳到的中间点
//                if(arr[i+j]==true){
//                    //说明找到一个可以到达终点的中间点
//                    arr[i]=true;//设置为true
//                    break;//提前结束循环，后面不管还有没有其他的也可以作为中间点的已经没有意义了
//                }
//            }
//        }
//        return arr[0]?true:false;//如果arr[0]为true，说明第一个能跳到最后一个，所以返回true

        //解法二：看了力扣题解得到的启发
        //应该算是贪心算法
        //这种方法采用的是从头到尾的方式
        int max=0;//max用来表示当前已经遍历过的点能到达的最远的数组下标，而下标<=max值的数组的点都要被遍历一遍
        int len=nums.length;
        if(len==1)
            return true;//起点已经是终点
        for (int i = 0; i <= max; i++) {
            int temp=i+nums[i];
            if(temp>max)
                max=temp;
            if(max>=len-1)//在遍历的过程中如果已经能到达的点加上该点能跳的步数已经能到达最后一个点了，则可以
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution_55 s = new Solution_55();
        int arr[]=new int[]{3,2,1,0,4};
        System.out.println(s.canJump(arr));
    }
}
